package com.jinan.algorithm.greedy;

import java.util.*;

public class GreedyTest {
    /**
     * 1705.吃苹果的最大数目 <a href="https://leetcode-cn.com/problems/maximum-number-of-eaten-apples/">...</a>
     * 难度：中等
     * tag：贪心算法
     * 描述：有一棵特殊的苹果树，一连 n 天，每天都可以长出若干个苹果。在第 i 天，树上会长出 apples[i] 个苹果，
     * 这些苹果将会在 days[i] 天后（也就是说，第 i + days[i] 天时）腐烂，变得无法食用。也可能有那么几天，
     * 树上不会长出新的苹果，此时用 apples[i] == 0 且 days[i] == 0 表示。
     * 你打算每天 最多 吃一个苹果来保证营养均衡。注意，你可以在这 n 天之后继续吃苹果。
     * 请你返回你可以吃掉的苹果的最大数目。
     * 提示：
     * apples.length == n
     * days.length == n
     * 1 <= n <= 2 * 10^4
     * 0 <= apples[i], days[i] <= 2 * 10^4
     * 只有apples[i] == 0  implies day[i] == 0才成立
     *
     * @param apples 苹果数量
     * @param days   腐烂时间
     * @return 最大吃掉的苹果数量`
     */
    public int eatenApples(int[] apples, int[] days) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        int ans = 0;
        for (int i = 0; i < apples.length || !pq.isEmpty(); i++) {
            //如果还在数组范围内，且当天有苹果，则加入优先队列
            if (i < apples.length && apples[i] > 0) {
                pq.offer(new int[]{i + days[i], apples[i]});
            }
            //弹出过期的苹果
            while (!pq.isEmpty() && pq.peek()[0] <= i) {
                pq.poll();
            }
            if (!pq.isEmpty()) {
                //吃一个最早腐烂的苹果
                ans++;
                pq.peek()[1]--;
                if (pq.peek()[1] == 0) {
                    pq.poll();
                }
            }
        }
        return ans;
    }

    /**
     * 3219.切蛋糕的最小总开销 II <a href="https://leetcode-cn.com/problems/minimum-cost-of-buying-candies-with-discount/">...</a>
     * 难度：困难
     * tag：贪心 数组 排序
     * description：
     * 有一个 m x n 大小的矩形蛋糕，需要切成 1 x 1 的小块。
     * 给你整数 m ，n 和两个数组：
     * horizontalCut 的大小为 m - 1 ，其中 horizontalCut[i] 表示沿着水平线 i 切蛋糕的开销。
     * verticalCut 的大小为 n - 1 ，其中 verticalCut[j] 表示沿着垂直线 j 切蛋糕的开销。
     * 一次操作中，你可以选择任意不是 1 x 1 大小的矩形蛋糕并执行以下操作之一：
     * 沿着水平线 i 切开蛋糕，开销为 horizontalCut[i] 。
     * 沿着垂直线 j 切开蛋糕，开销为 verticalCut[j] 。
     * 每次操作后，这块蛋糕都被切成两个独立的小蛋糕。
     * 每次操作的开销都为最开始对应切割线的开销，并且不会改变。
     * 请你返回将蛋糕全部切成 1 x 1 的蛋糕块的 最小 总开销。
     * 提示：
     * 2 <= m, n <= 10^6
     * horizontalCut.length == m - 1
     * verticalCut.length == n - 1
     * 1 <= horizontalCut[i], verticalCut[i] <= 10^3
     *
     * @param m             矩形蛋糕的高度
     * @param n             矩形蛋糕的宽度
     * @param horizontalCut 矩形蛋糕的高度切割线
     * @param verticalCut   矩形蛋糕的宽度切割线
     * @return 切蛋糕的最小总开销
     */
    public long minimumCost(int m, int n, int[] horizontalCut, int[] verticalCut) {
        Arrays.sort(horizontalCut);
        Arrays.sort(verticalCut);
        long ans = 0;
        int i = 0;
        int j = 0;
        while (i < m - 1 || j < n - 1) {
            if (j == n - 1 || i < m - 1 && horizontalCut[i] < verticalCut[j]) {
                ans += (long) horizontalCut[i++] * (n - j);
            } else {
                ans += (long) verticalCut[j++] * (m - i);
            }
        }
        return ans;
    }

    /**
     * 135.分发糖果 <a href="https://leetcode-cn.com/problems/candy/">...</a>
     * 难度：困难
     * tag：贪心算法 数组
     * description：
     * n个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
     * 你需要按照以下要求，给这些孩子分发糖果：
     * 每个孩子至少分配到 1 个糖果。
     * 相邻两个孩子评分更高的孩子会获得更多的糖果。
     * 请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
     *
     * @param ratings 评分
     * @return 最少糖果数目
     */
    public int candy(int[] ratings) {
        int n = ratings.length;
        int[] candy = new int[n];
        Arrays.fill(candy, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candy[i] = candy[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candy[i] = Math.max(candy[i], candy[i + 1] + 1);
            }
        }
        return Arrays.stream(candy).sum();
    }

    /**
     * 2434.使用机器人打印字典序最小的字符串
     * 难度：中等
     * tag: 栈 贪心算法 字符串
     * description：给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：
     * 删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
     * 删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。
     * 请你返回纸上能写出的字典序最小的字符串。
     * restriction：
     * 1 <= s.length <= 10^5
     * s 仅由小写英文字母组成
     *
     * @param s 字符串
     * @return 字符串
     */
    public String robotWithString(String s) {
        int n = s.length();
        char[] suf_min = new char[n + 1];
        suf_min[n] = Character.MAX_VALUE;
        suf_min[n - 1] = s.charAt(n - 1);
        for (int i = n - 2; i >= 0; i--) {
            suf_min[i] = (char) (Math.min(s.charAt(i), suf_min[i + 1]));
        }
        Deque<Character> stack = new ArrayDeque<>();
        StringBuilder ans = new StringBuilder(n);
        for (int i = 0; i < n; i++) {
            stack.push(s.charAt(i));
            while (!stack.isEmpty() && stack.peek() <= suf_min[i + 1]) {
                ans.append(stack.pop());
            }
        }
        return ans.toString();
    }

    /**
     * 3170.删除星号以后字典序最小的字符串
     * 难度：中等
     * tag:栈 贪心 哈希表 字符串 堆（优先队列）
     * description:给你一个字符串 s 。它可能包含任意数量的 '*' 字符。你的任务是删除所有的 '*' 字符。
     * 当字符串还存在至少一个 '*' 字符时，你可以执行以下操作：
     * 删除最左边的 '*' 字符，同时删除该星号字符左边一个字典序 最小 的字符。如果有多个字典序最小的字符，你可以删除它们中的任意一个。
     * 请你返回删除所有 '*' 字符以后，剩余字符连接而成的 字典序最小 的字符串。
     * restriction:
     * 1 <= s.length <= 10^5
     * s 仅由小写英文字母和 '*' 组成
     * 输入保证操作可以删除所有的 '*' 字符。
     *
     * @param s 字符串
     * @return 字符串
     */
    public String clearStars(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        boolean[] toRemove = new boolean[n]; // 标记要删除的字符
        // 优先队列按字符升序排列，字符相同则按索引降序（保证取最右边的）
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) ->
                a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]
        );

        for (int i = 0; i < n; i++) {
            if (chars[i] == '*') {
                if (!pq.isEmpty()) {
                    int[] min = pq.poll(); // 取出当前最小字符
                    toRemove[min[1]] = true; // 标记该字符为待删除
                }
            } else {
                // 存储字符的ASCII值和索引到队列
                pq.offer(new int[]{chars[i], i});
            }
        }

        // 构建结果字符串（跳过被标记的字符和星号）
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (chars[i] != '*' && !toRemove[i]) {
                sb.append(chars[i]);
            }
        }
        return sb.toString();
    }

    /**
     * 1792.最大平均通过率 <a href="https://leetcode-cn.com/problems/maximum-average-pass-ratio/">...</a>
     * 难度：中等
     * tag：贪心 数组 堆（优先队列）
     * description：
     * 一所学校里有一些班级，每个班级里有一些学生，现在每个班都会进行一场期末考试。给你一个二维数组 classes ，其中 classes[i] = [passi, totali] ，表示你提前知道了第 i 个班级总共有 totali 个学生，其中只有 passi 个学生可以通过考试。
     * 给你一个整数 extraStudents ，表示额外有 extraStudents 个聪明的学生，他们 一定 能通过任何班级的期末考。你需要给这 extraStudents 个学生每人都安排一个班级，使得 所有 班级的 平均 通过率 最大 。
     * 一个班级的 通过率 等于这个班级通过考试的学生人数除以这个班级的总人数。平均通过率 是所有班级的通过率之和除以班级数目。
     * 请你返回在安排这 extraStudents 个学生去对应班级后的 最大 平均通过率。与标准答案误差范围在 10-5 以内的结果都会视为正确结果。
     * restriction:
     * 1 <= classes.length <= 10^5
     * classes[i].length == 2
     * 1 <= passi <= totali <= 10^5
     * 1 <= extraStudents <= 10^5
     * @param classes 二维数组
     * @param extraStudents 额外学生数
     * @return 最大平均通过率
     */
    public double maxAverageRatio(int[][] classes, int extraStudents) {
        PriorityQueue<double[]> pq = new PriorityQueue<>((a, b) -> {
            // 比较增加一个学生后通过率的提升幅度
            double ratioDiffA = (a[0] + 1) / (a[1] + 1) - a[0] / a[1];
            double ratioDiffB = (b[0] + 1) / (b[1] + 1) - b[0] / b[1];
            return Double.compare(ratioDiffB, ratioDiffA); // 最大堆
        });
        for (int[] clazz : classes) {
            pq.offer(new double[]{clazz[0], clazz[1]});
        }
        while (extraStudents-- > 0) {
            double[] clazz = pq.poll();
            if (clazz!=null) {
                clazz[0]++;
                clazz[1]++;
                pq.offer(clazz);
            }
        }
        double sum = 0;
        while (!pq.isEmpty()) {
            double[] clazz = pq.poll();
            sum += clazz[0] / clazz[1];
        }
        return sum / classes.length;
    }

    /**
     * 1733. 需要教语言的最少人数<a href="https://leetcode-cn.com/problems/minimum-number-of-people-to-teach/">...</a>
     * 难度：中等
     * tag：贪心 数组 矩阵 堆（优先队列） 哈希表
     * description：
     * 在一个由 m 个用户组成的社交网络里，我们获取到一些用户之间的好友关系。两个用户之间可以相互沟通的条件是他们都掌握同一门语言。
     * 给你一个整数 n ，数组 languages 和数组 friendships ，它们的含义如下：
     * 总共有 n 种语言，编号从 1 到 n 。
     * languages[i] 是第 i 位用户掌握的语言集合。
     * friendships[i] = [ui, vi] 表示 ui 和 vi 为好友关系。
     * 你可以选择 一门 语言并教会一些用户，使得所有好友之间都可以相互沟通。请返回你 最少 需要教会多少名用户。
     * 请注意，好友关系没有传递性，也就是说如果 x 和 y 是好友，且 y 和 z 是好友， x 和 z 不一定是好友。
     * restriction:
     * 2 <= n <= 500
     * languages.length == m
     * 1 <= m <= 500
     * 1 <= languages[i].length <= n
     * 1 <= languages[i][j] <= n
     * 1 <= ui < vi <= languages.length
     * 1 <= friendships.length <= 500
     * 所有的好友关系 (ui, vi) 都是唯一的。
     * languages[i] 中包含的值互不相同。
     * @param n 用户数
     * @param languages 语言
     * @param friendships 好友关系
     * @return 最少需要教会的用户数
     */
    public int minimumTeachings(int n, int[][] languages, int[][] friendships) {
        int m = languages.length;
        Set<Integer>[] languageSets = new Set[m];
        for (int i = 0; i < m; i++) {
            languageSets[i] = new HashSet<>();
            for (int language : languages[i]) {
                languageSets[i].add(language);
            }
        }
        int [] languageCount = new int[n+1];
        Set<Integer> unknown = new HashSet<>();
        for (int[] friendship : friendships) {
            int i = friendship[0] - 1;
            int j = friendship[1] - 1;
            Set<Integer> intersection = new HashSet<>(languageSets[i]);
            intersection.retainAll(languageSets[j]);
            if(intersection.isEmpty()){
                if(!unknown.contains(i)){
                    unknown.add(i);
                    for (int k : languageSets[i]){
                        languageCount[k]++;
                    }
                }
                if (!unknown.contains(j)){
                    unknown.add(j);
                    for (int k : languageSets[j]){
                        languageCount[k]++;
                    }
                }
            }
        }
        int max = Integer.MIN_VALUE;
        for(int i = 1; i <= n; i++){
            if(max <languageCount[i]){
                max = languageCount[i];
            }
        }
        return unknown.size() - max;
    }
}
